1. Field of the Invention
The present invention generally relates to color halftoning techniques for printers and facsimile machines and, more particularly, to a method and apparatus for halftoning for color printing with the constraint that all elementary colors may not be printed at the same spot and/or that the bandwidth to the printer requires a constraint on the colors printed at the same spot and subsequent spots.
2. Background Description
Digital halftoning is a technique for printing a picture (or more generally, displaying it on some two-dimensional medium) using small dots with a limited number of colors such that it appears to consist of many colors when viewed from a proper distance. For example, a picture of black and white dots can appear to display grey colors when viewed from some distance.
The fastest and most commonly used methods for digital halftoning are dithering algorithms which use threshold arrays, also called dither matrices or dither masks. Error diffusion, as first described in xe2x80x9cAn Adaptive Algorithm for Spatial Greyscalexe2x80x9d by R. W. Floyd and L. Steinberg, Proceeding of the SID 17/2, (1976) pp. 75-77, is another popular technique for halftoning used today and is considered to be one of the best, and the best among the techniques with similar operating time. These techniques and others are reviewed in the book Digital Halftoning, MIT Press, Cambridge, Mass. (1987) by R. Ulichney, which is a general reference for digital halftoning.
The problem of digital halftoning has also to be considered for digital color printers, as well as various other digital color display devices. Both dithering and error diffusion methods have been adapted to color.
In the sequel, we will use the word xe2x80x9cinkxe2x80x9d to refer to any coloring substance such as ink or toner to be used by the printer and also to the color generation method in displays. Also, for definiteness, in the rest of this disclosure, we will assume colors are represented in the C, M, Y (cyan, magenta, yellow) space, although more general cases could be treated as well by the present invention. As is often the case in digital color printing, we assume first that at each pixel, the printer can either print:
white (or W, i.e., no ink is deposited),
cyan (or C),
magenta (or M),
yellow (or Y),
red (or R, i.e., M and Y are both printed),
green (or G, i.e., Y and C are both printed),
blue (or B, i.e., C and M are both printed), or
black (or K).
Depending on the printer, black is either a separate ink or consists of the superposition of C, M and Y.
A simple way of performing digital halftoning in color consists in separating the colors according to their C, M and Y components, and treating each component separately, either using a dithering method, an error diffusion method, or any other suitable monochromatic digital halftoning method. One has to take some precautions when doing this to avoid moire patterns. This, and other classical approaches to color halftoning is described for instance in xe2x80x9cColor Technology for Electronic Imaging Devicesxe2x80x9d by Henry Kang, SPIE Optical Engineering Press, 1997 ISBN 0-8194-2108-1, which is a general reference for this subject.
Some printers have specific constraints (e.g., hardware constraints, software constraints, type of use, cost, etc.) which prevent the use of classical dithering methods for color images. We consider here the case of a digital printer with four inks, say C, M, Y, and K (black) for definiteness, such that the printer can only print at most one of these colors at each pixel. Thus, each pixel of the printed image has color either W, C, M, Y, or K. We call this restriction the single color constraint. An example of such a printer with this color constraint is a printer that has a ribbon with four color bands along the length of the ribbon. The command data stream allows the ribbon to be raised and lowered so that just one of the four bands is struck to print one of the four colors for each pixel.
This invention can easily be adapted to printers with other inks, for example, R (red), G (green) and B (blue) and even to the case when the color of the paper is not white. Such a printer with the single color constraint was discussed in U.S. Pat. No. 5,633,990 for xe2x80x9cMethod of Non-Overlapping Color Printingxe2x80x9d issued to Edward M. Housel. In the Housel patent, a solution is disclosed for halftoning color images. This solution consists of halftoning each of the primary color planes and assigning a configuration of printed dots to each pixel in the halftoned image. This solution has several disadvantages, the main one of which is that a printing resolution higher than the image resolution is required. The presently disclosed method operates in a completely different way and can print at the same resolution as the image.
More generally, if there are ink activators for n elementary colors, say A1, A2, . . . , An, it may be the case that the number of colors that can be printed at each pixel is smaller than n. We call this restriction the limited color constraint. Besides limited data transmission bandwidth, other reasons to accept and/or impose limited color constraints are printing technology, cost of inks and constraints on the amount of liquid and/or drying time that the paper can accommodate. Observe, that the limited color constraint reduces the gamut of the printer considerably.
We also consider the problem posed by printers such that the bandwidth to the guns (or other color activators) is so small that long sequences of pixels of the same color along a line are preferred to allow for more compact information streams. We call this restriction the long segments constraint. Anybody versed in the art would readily understand why these constraints can be imposed to satisfy low bandwidth in the transmission of instructions to the guns. In particular, long segments of pixels with the same color is especially amenable to run length encoding.
A typical case in which the invention applies are devices with low or variable bandwidth such as facsimile machines, where one likes to have draft modes for faster (and less costly) transmission.
The third problem the present invention addresses is the problem of misregistration. Misregistration refers to the fact that the coordinates (i,j) do not necessarily correspond to the same location for all color activators, due to mechanical imprecision of the printer. In low end printers, this misregistration can fluctuate too much for any reasonable solution. In more expensive machines, this misregistration can be stable during the printing of several images. For full color printers, such misregistration is easily compensated by translation of the origin in the printing decision matrices. The printing decision matrices are the result of the halftoning process and are the arrays associated with each color activator, which tell where colors have to be printed.
The problem of misregistration of the color activators also occurs in printers with the limited color constraint. Under the single color constraint, or more generally under the limited color constraint, translation of the printing decision matrices cannot be used to compensate for misregistration as several color activators, more than allowed by the constraint, might need to print at the same coordinates (i,j). Consequently, another method has to be used to compensate for misregistration whenever a printer with the limited color constraint is used.
It is therefore an object of the present invention to provide a method that produces good approximations of full color images and solves the misregistration problem for printers with the above discussed constraints.
The constraints can be optionally enforced on all or parts of the image. Some reasons for imposing the constraints include limiting the amount of ink used, utilizing the apparatus in draft mode, improving compression of the halftoned image and local ink wetness control of the printed image.
For simplicity of the presentation, we will mostly discuss the case of single color constraint with color activators in the colors C, M, Y, and K. Anybody versed in the art of digital printing would readily understand how to adapt the invention to more general limited color constraints.
We denote by I the image to be printed. If the image has v columns and h rows of pixels, one can understand I as an h by v array of triples
I(i,j)=(C(i,j),M(i,j),Y(i,j).
For each pixel (i,j) where i is between 1 and h, j is between 1 and v, the values C(i,j),M(i,j),Y(i,j) in the triple I(i,j) are respectively the amount (which is a number normalized between 0 and 1) of the color C, M, and Y at pixel (i,j). In many cases, the C(i,j),M(i,j) and Y(i,j) values are given in the range of 0 to 255. The disclosed invention can be easily adapted to this case by means of simple normalization. The printed image P can be understood as an array of quadruples
P(i,j)=(c(i,j),m(i,j),y(i,j),k(i,j)).
For each pixel (i,j) where i is between 1 and h,j is between 1 and v, the values c(i,j), m(i,j), y(i,j), and k(i,j) (which are either 0 or 1) determine whether the color C, M, Y, and K is printed at pixel (i,j) respectively, with 0 meaning that the color is not printed, and 1 meaning that it is printed.
The single color constraint corresponds to the equation:
c(i,j)+m(i,j)+y(i,j)+k(i,j)=either 0 or 1.
According to the present invention, such an array P is computed for each array I using a digital halftoning method adapted to the constraint that at most a single ink can be deposited at each pixel and/or the long segments constraint. P is then considered as a new original image. Then, whenever one needs to print I, P is sent to the page formatting software or PostScript processor as if it were the original image I. Whichever method used by the page formatting software will then allow to print an image exactly corresponding to the specifications of the array P.
If the input image is of a lower resolution than the output image; e.g., 300 pixels per inch input and 600 pixels per inch output, then for every input pixel several output pixels may be printed (e.g., four output dots per input pixel). This scaling up of the input image could be done before any of the present invention""s operations, but at the cost of additional CPU (central processor unit) cycles and bandwidth.
It may happen that the guns, or more generally the color activators, for the colors C, M, Y, and K are misregistered. If the defect of registration is fluctuating too much as in some low end printers, the best choice is possibly to ignore it. We assume that the misregistration only changes slowly and that the changes are measured, and that it has been rounded off to some integer number of pixels horizontally and vertically. With such misregistration information, when printing with a unconstrained full color printer, one can simply shift the printing decision matrices corresponding to each color so as to compensate for the misregistration. This simple solution cannot be used in the case of single color constraints as it could induce several guns to get a 1 (i.e., print) for the same (i,j). To overcome this difficulty, the shift will be made at the level of the image I. The image I is first decomposed into the colors C(i,j),M(i,j),Y(i,j) and K(i,j) according to any well known decomposition and then into the image Txe2x80x3 by shifting the matrices C(i,j),M(i,j),Y(i,j), and K(i,j) accordingly to compensate for the misregistration. This results in a somewhat scrambled image Ixe2x80x3. Image Ixe2x80x3, after converting back to CMY space, is then halftoned using the disclosed method for halftoning images with a single color constraint. In the sequel, whenever we mention the matrix I, it may be either I, or Ixe2x80x3 in case misregistration has been compensated for. This procedure can be easily modified to compensate for other types of misregistration, such as the case where the pixels from the different color activators are rotated with respect to each other.
The digital halftoning of I will be done in two stages to take into account the constraints of the printer. The first stage compensates for the fact that, because only at most one of C, M, Y, and K can be printed at each pixel, the printable gamut will necessarily be seriously reduced. One thus begins by choosing a gamut reduction map F from the conventional full color unit cube spanned by C, M, and Y (denoted by Q=[0,1]3) to a set of colors representing the gamut G of the printer, or just the gamut G0 corresponding to the single color constraint: one can then compute F(I), where all colors belong to the constructed color set representing G or G0. Then, some form of digital halftoning is used, so that the single color constraint is satisfied: one can either use some form of pseudo-mask method, i.e., a dither mask whose threshold values are interpreted according to the color to be printed, or a vector error diffusion method (both pseudo-masks and vector error diffusion will be explained in the sequel to the extent necessary for the present invention). Alternatively, one can choose a decomposition of the color pixels in F(I) into the components C, M, Y, K, and W and use an adapted form of error diffision. Whenever an error diffusion approach is chosen, one can modify it by using some classical method in the prior art to better the results of error diffusion. It is clear that the halftoning method used cannot be simply decomposition into primary colors and halftoning each color plane independently since that might result in halftoned images violating the required constraints.